1. Technical Field
The present invention relates to methods for automatically placing circuit elements in an arrangement suitable for placement on an integrated circuit chip, and more particularly relates to a method for expanding the capability of horizontal channel based placement algorithms to incorporate non-conforming circuit elements.
2. Background Art
In integrated circuit design, typically, thousands of transistors must be arranged in a limited space to provide some desired logical function. To assist designers in this process, placement methods have been developed and implemented in computer programs. One such placement method is the standard cell horizontal channel based placement method. According to this method, a library of standard cells is provided, each such cell containing a small group of transistors that together provide an elemental logical function, such as AND gate, OR gate, or the like. The logical designer utilizes these standard cells as building blocks in constructing the overall circuit that implements the larger logical function. The horizontal channel based placement algorithm takes this logical arrangement of standard cells that the logical designer has created and physically arranges them optimally in an area usually referred to as the Standard Cell Block that corresponds to the limited area available for placement on an area in the integrated circuit chip itself.
The standard cells are physically limited in height to a specific maximum. The horizontal channel based placement method utilizes a field comprising a stack of parallel limit lines defining a stack of rows, such limit lines having a minimum spacing equal to the specific maximum height of the standard cells, and arranges the cells within these rows.
Given a particular library of standard cells, there is typically a preferred implementation for certain critical path portions of the overall circuit that provides superior performance, density, low power or function. It may be desired, therefore, to prearrange the circuits for such critical path portions into fixed macro blocks, rather than rely on the standard cell implementation.
A problem, however, is that such macro blocks do not, in general, conform to the restrictions of the placement and routing algorithms applied to the standard cell block construction. In particular, the height of such macro blocks typically exceed by several multiples the specified standard cell maximum. Unmodified, such placement methods are simply unable to handle these macro blocks.
Several approaches have been discussed for modifying the standard cell placement method to permit its use in conjunction with circuit portions preconfigured as macro blocks. For example, B. Korte, et al., in "Combining Partitioning and Global Routing in Sea-Of-Cells Design" ICCAD/IEEE Proceedings, p. 98 (1989), discuss an approach which utilizes partitioning and global routing in a type of horizontal channel based placement method known as Sea-Of-Cells design. According to the approach disclosed in this article, the macro blocks are prepositioned and fixed at certain locations within the standard cell blocks, and the remaining area of the block is partitioned into regions to which the standard cells are assigned. The standard cells are then placed within their assigned regions using a Sea-Of-Cells placement method. While this approach does result in the mixed placement of macros and standard cells with Sea-Of-Cells placement methods, a disadvantage is that the macro blocks are not optimally placed with respect to the surrounding standard cells.
Another approach is discussed by M. Upton, et al, in "Integrated Placement for Mixed Macro Cell and Standard Cell Designs," 27th ACM/IEEE Design Automation Conference, p. 32 (1990). According to this approach, the standard cells are partitioned into blocks using a known minimum net-cut method, and then these blocks, along with the macro blocks, are placed using a simulated annealing optimization method. Then, a simple simulated annealing method is used to place the standard cells within the blocks. This approach has an advantage over the Korte, et al. approach in that the macro blocks are placed in optimized locations within the standard cell block. However, a disadvantage of this approach is that it is quite complex, resulting in the use of considerable time in deriving an implementation as well as resulting in considerable CPU time in executing such implementation.
A third approach is disclosed by A. DiGiacomo, et al., in U.S. Pat. No. 4,630,219, commonly assigned, which issued on Dec. 16, 1986. According to the method disclosed in this patent, the overall circuit is partitioned into blocks, including the macro blocks. A three pass process is then applied to these resulting elements. In the first pass, all of the elements are treated as if they are the same size, are assigned to element positions, and their placement is optimized. In the second pass, these unit size elements are replaced by macro size elements which are approximately the actual size of the corresponding electronic elements. The macro size elements are then rearranged for optimal placement on a macro model image, taking their sizes and shapes into account. Finally, the macro size elements are replaced by actual size elements, and their placement is again optimized. In this method, as in the previous method, the macro blocks are placed according to a method designed to optimize their position. However, it is desired to have a simplier method to permit the utilization of macro blocks with horizontal channel based placement methods.
Other U.S. Patents disclosing approaches to integrated circuit placement which contain large circuit blocks are as follows:
U.S. Pat. No. 4,908,772, issued to M. C. Chi on Mar. 13, 1990, and assigned to Bell Telephone Laboratories, discloses a placement method which involves global partitioning of standard cells into clusters that are then placed among the macro blocks.
U.S. Pat. No. 4,890,238, issued to K. Klein, et al., on Dec. 26, 1989, commonly assigned, discloses a method for physical chip design that also utilizes the technique of global partitioning and arranging.
U.S. Pat. No. 4,593,363, issued to M. Burstein, et al., on Jun. 3, 1986, and commonly assigned, discloses a placement method that also utilizes the technique of partitioning.
U.S. Pat. No. 4,577,276, issued to A. E. Dunlop, et al, on Mar. 18, 1986, and assigned to AT&T Bell Laboratories, discloses a placement method that also uses partitioning.
It is thus an object of the present invention to provide a method for automatically and optimally embedding macro blocks in a horizontal channel based placement method implemented in a computer program without the need for manual edge placement and without the need to partition.
It is a further object to provide such a method for embedding a plurality of macro blocks within a standard cell circuit structure.
It is a still further object of the invention to provide such a method that can be implemented in a relatively simple and straightforward manner.